We will manually trace Dijkstra's Algorithm using a weighted graph to understand how distances are updated.
- We use the standard weighted, directed graph example for this trace, shown on the right.
- The goal is to find the shortest path from the source node 'A' to all other nodes.
- We must track two key data structures at every step: the distances array and the Priority Queue (PQ).
- The trace begins with the critical Initialization Step, setting up the initial state of our data structures.
Initialization State: Data Structures
| Node | Current distances | previous | visited |
|---|---|---|---|
| A | 0 | None | False |
| B | $\infty$ | None | False |
| C | $\infty$ | None | False |
| D | $\infty$ | None | False |